#include <stdio.h>
#include <stdlib.h>
#include "tree.h"

Node* insertIntoTree(Node* root, int index, char value);
Node* CreateTree(Node* root)
{
    Node* item = NULL;
    char value;
    int index = 0;
    while(1) {
	value = getchar();
	if(value == '0') 
	    break;
	root = insertIntoTree(root, index, value);
	index ++;
    }
    return root;
}

Node* insertIntoTree(Node* root, int index, char value) 
{
    Node* p = root,*q;
    int i = 0;
    if(root == NULL) {
	root = (Node*)malloc(sizeof(Node));
	root -> index = index;
	root -> value = value;
	root -> leftChild = NULL;
	root -> rightChild = NULL;
    }
    else {
	while ( p != NULL) {
	    q = p;
	    if(p -> value < value) {
		p = p -> rightChild;
		i = 0;
	    }
	    else {
		p = p -> leftChild;
		i = 1;
	    }
	}
	if(i == 0) {
	    q ->rightChild = (Node*)malloc(sizeof(Node));
	    q -> rightChild -> value = value;
	    q -> rightChild -> index = index;
	    q -> rightChild -> rightChild = NULL;
	    q -> rightChild -> leftChild = NULL;
	}
	else {
	    q -> leftChild = (Node*)malloc(sizeof(Node));
	    q -> leftChild -> index = index;
	    q -> leftChild -> value = value;
	    q -> leftChild -> leftChild = NULL;
	    q -> leftChild -> rightChild = NULL;
	}
    }
    return root;
}
